1. Field of the Invention
This invention relates to a digital computer system having an error correction code (ECC) system for generating ECC syndromes on digital words to be stored or transmitted. An ECC re-encoder for generating syndromes on the digital words as they are removed from storage or after transmission is included, as well as a comparator for comparing the pre-storage/pre-transmission syndromes with the post-storage/post-transmission syndromes. More particularly, it pertains to an ECC system in which the comparator is included in and is a part of the re-encoder.
2. Description of the Related Art
In data processing systems it has been necessary to have circuitry which checks data that has been transmitted between system units or which has been stored in system memories and detects errors which may have been introduced during the transmission or storage operations. Error detection and correction is especially necessary in systems in which data transmissions or storage is performed at high speeds because such systems are more prone to disturbances by noise and other erroneous signals.
Many prior art systems have been developed to protect data stored in memories and data which is transmitted between data processing circuits. Simple parity checking was done in the past to effectively count the number of ones in a digital word, and if odd, assign a one parity bit and if even, assign a zero parity bit (odd parity). Typically, a parity generator adds the parity check bit to each word before transmission. In such a manner, odd sets automatically become even with the extra one and even sets remain unchanged by the extra zero.
In such parity checking systems, an error in a single digit or bit in a data word is discernable since the parity check bit associated with that data word containing an error is the reverse from what is expected. To confirm that the bits have not changed after each transmission or storage, thereby indicating that no error has occurred, the number of ones in each word are recounted and, if the result is an odd number for an even parity system or if the result is an even number for an odd parity system, the result indicates that one of the bits in the data word is in error.
After detection of an error, such systems are often configured to retrieve or recreate the original data word, for example by requesting a repeat transmission of the original data word before continuing processing, thereby correcting the error. Others of such systems are configured to simply output a signal indicating to the user that an error has occurred. One drawback to such systems is that only errors in an odd number of digits can be detected with a single parity check, since an even number of errors results in the parity expected for a correct transmission. Furthermore, the specific bit in error cannot be identified by the parity check procedure described herein. To correct a single incorrect bit, the entire data word, including both correct and incorrect bits, must be reproduced. Thus, parity checking words works most effectively when the errors are few and far between. Finally, parity checking is not adequate as a defense against data errors when there is a permanent defect in the memory cell or other storage element that makes retransmission ineffective as a remedy. Such situations call for more elaborate coding strategies capable of correcting the problem as well as detecting it.
It has been widely recognized that error detection and/or correction is desirable in situations where an input digital word is operated upon in a manner having a significant probability of inadvertent alteration of at least one of the bits. Accordingly, it is common in modern digital computer systems to incorporate an error detection and/or correction scheme selected to provide a desired level of reliability at an acceptable cost. For example, simple parity check techniques as described above are generally satisfactory when the number of words is limited. Block error correction techniques have found use in systems which involve very large numbers of words and hence a higher probability of error.
A block error correction code is described in detail in the Bell System Technical Journal Volume XXIX, April 1950, Number 2 entitled "Error Detecting and Error Correcting Codes" by R. W. Hamming. This code has been used extensively over the years in connection with relatively short binary words. For example, a 16 bit input word requires a 6 bit Hamming Code to provide a capability of detecting two errors and correcting one within that 16 bit word. A 32 bit input word requires a 7 bit Hamming Code to provide a capability of detecting two errors and correcting one within that 32 bit word. This capability is essential in those systems that use a very large number of words (very large memory).
The Hamming Code is a system of multiple parity checks that encodes data words in a logical manner so that single errors can be not only detected but also identified for correction. A transmitted data word used in the Hamming Code consists of the original data word and parity check digits appended thereto. Each of the required parity checks is performed upon the specific bit positions of the transmitted word. The system enables the isolation of an erroneous digit, whether it is in one of the original data bits or in one of the added parity check bits. If all of the parity check operations are performed successfully, the data word is assumed to be error free. If one or more of the check operations is unsuccessful, however, a single bit error is uniquely determined by decoding so-called syndrome bits which are derived from the parity check bit.
In the prior art, incoming digital words have had ECC syndromes generated and stored in the memory along with the associated digital word. The word and syndrome are both read from memory and a new syndrome is generated from the word read from memory. After having generated this new syndrome, it is compared with the original syndrome stored in the memory. The syndrome generation and comparison is done in two separate and distinct steps.
According to the present invention, the comparison between the two syndromes begins at the first and second levels of the generation of the new syndrome.